package leetcode;

public class Lc547 {

    int[] parent;
    int cnt = 0;

    public int findCircleNum(int[][] isConnected) {

        cnt = isConnected.length;
        parent = new int[isConnected.length];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (i != j && isConnected[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        return cnt;
    }

    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y) {
        int xp = find(x);
        int yp = find(y);
        if (xp != yp) {
            parent[xp] = yp;
            cnt--;
        }
    }
}
